/*
 * @lc app=leetcode.cn id=435 lang=javascript
 *
 * [435] 无重叠区间
 */

// @lc code=start
/**
 * @param {number[][]} intervals
 * @return {number}
 */
var eraseOverlapIntervals = function (intervals) {
  const size = intervals.length;
  if (!size) {
    return 0;
  }

  intervals.sort((a, b) => a[1] - b[1]);

  // 求最大区间范围
  const dp = new Array(size).fill(1);

  for (let i = 1; i < size; i++) {
    for (let j = 0; j < i; j++) {
      if (intervals[j][1] <= intervals[i][0]) {
        dp[i] = Math.max(dp[i], dp[j] + 1);
      }
    }
  }

  return size - Math.max(...dp);
};
// @lc code=end
